我要招人

去企业版

首页 > 试题广场 >

大数乘法

[编程题]大数乘法

热度指数：29065 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

数据范围：读入的数字大小满足 $0 \le n \le 10^{1000}$

要求：空间复杂度 $O(m)$ ，时间复杂度 $O(m^2)$ （假设m是n的长度）

示例1

输入

"11","99"

输出

"1089"

说明

11*99=1089

示例2

输入

"1","0"

输出

"0"

算法知识视频讲解

Python 3

昊天明月

python 真的赖啊

发表于 2023-04-29 14:44:50 回复(0)

Python 3

danspace

class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        return str(eval(s+'*'+t))

发表于 2022-04-24 14:59:10 回复(0)

Python 3

Lasheverything

累死我了。。应该没人看

class Solution:
    def solve(self, s: str, t: str) -> str:
        # write code here
        ret = []
        for k in range(0, len(s) + 1):  # 最多位数
            ret.append(0)  # 小位在前

        
        for i in range(-1, -len(t) - 1, -1):
            add_number = 0
            for j in range(-1, -len(s) - 1, -1):
                number = int(t[i])
                up_number = int(s[j])  # 乘法写法上面的数
                N = number * up_number + add_number + ret[j + (i + 1)]  # 单词乘法结果
                loc_number = N % 10  # 记下数

                ret[j + (i + 1)] = loc_number # (i+1) 控制错位相加

                add_number = N // 10  #  进位
            
            self.check_add(ret) # 检查进位，补充位数
            
            if add_number > 0:
                ret[j + (i + 1)-1] = ret[j + (i + 1)-1] + add_number

        ret = [str(v) for v in ret]
        # 去掉字符串开头的0
        i = 0
        while i < len(ret) and ret[i] == '0':
            i += 1
        if i == len(ret): # 字符串全部为0
            return '0'
        else:
            return ''.join(ret[i:])
        return "".join(ret)
    
    def check_add(self, ret):
        # 不管是否有进位，在最高位前补充两个位，赋值为0
        zero = 0
        for i in range(0, len(ret)):
            if ret[i] == 0:
                zero += 1
            if ret[i] > 0:
                break
            for i in range(2 - zero):
                ret.insert(0, 0)

发表于 2022-03-24 16:11:28 回复(0)

Python 3

牛客38477449号

class Solution:
    def solve(self , s , t ):
        # write code here
        m, n = len(s), len(t)
        arr = [0] * (m + n)
        for i in range(m):
            for j in range(n):
                arr[i+j+1] += int(s[i]) * int(t[j])
        info = 0
        for k in range(len(arr)-1, -1, -1):
            if arr[k] + info >= 10:
                temp = arr[k]
                arr[k] = (info + arr[k]) % 10
                info = (info + temp) // 10
            else:
                arr[k] += info
                info = 0
        arr[0] += info
        res = ''.join([str(num) for num in arr]).strip('0')
        return res if res else '0'

发表于 2021-09-15 01:08:05 回复(0)

Python 3

Virtual~

class Solution:
    def solve(self , s , t ):
        # write code here
        return str(int(s)*int(t))

发表于 2021-09-13 21:55:21 回复(0)

Python 3

VincentLau~

class Solution:
    def solve(self , s , t ):
        # write code here
        def multiply(a, b):
            b = int(b)
            res, carry = "", 0
            for c in a:
                tmp = int(c) * b + carry
                res += str(tmp % 10)
                carry = tmp // 10
            if carry:
                res += str(carry)
            return res
        s, t = s[::-1], t[::-1]
        if len(s) < len(t): n1, n2 = t, s
        else: n1, n2 = s, t
        res = []
        for c in n2:
            tmp = multiply(n1, c)
            res.append(int(tmp[::-1]))
        ans = 0
        for num in res[::-1]:
            ans = 10*ans + num
        return str(ans)

发表于 2021-08-14 18:22:51 回复(0)

Python 3